package com.algorithm.recursive;

/**
 * 跳台阶扩展问题
 * 题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法
 * 思路：首先可以看出目前已经不是斐波那契数列；所以我们应该确定一下这个算法的表达式：
 * 1阶 一种方法
 * 2阶 两种方法  1-1,2
 * 3阶 四种方法 1-1-1,1-2,2-1,3
 * 4阶 八种方法 1-1-1-1,1-1-2,1-2-1,1-3,2-1-1,2-2,3-1,4
 * 5阶 16种方法 1-1-1-1-1,1-1-1-2,1-1-3,1-4,1-1-2-1,1-2-1-1,1-2-2,1-3-1,2-1-1-1,2-1-2,2-2-1,2-3,3-1-1,3-2,4-1,5
 * 可以总结出公式为 2的n-1 次方
 */
public class JumpFloorII {

    public static void main(String[] args) {
        System.out.println(jumpFloorII(4));

    }
    public static int jumpFloorII(int target) {
        if (target <= 0) return 0;
        return (int) Math.pow(2, target - 1);
    }
}
